DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2015.33

Non Trivial Computations in Anonymous Dynamic Networks

Authors: Giuseppe Di Luna and Roberto Baldoni

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract

In this paper we consider a static set of anonymous processes, i.e., they do not have distinguished IDs, that communicate with neighbors using a local broadcast primitive. The communication graph changes at each computational round with the restriction of being always connected, i.e., the network topology guarantees 1-interval connectivity. In such setting non trivial computations, i.e., answering to a predicate like "there exists at least one process with initial input a?", are impossible. In a recent work, it has been conjectured that the impossibility holds even if a distinguished leader process is available within the computation. In this paper we prove that the conjecture is false. We show this result by implementing a deterministic leader-based terminating counting algorithm. In order to build our counting algorithm we first develop a counting technique that is time optimal on a family of dynamic graphs where each process has a fixed distance h from the leader and such distance does not change along rounds. Using this technique we build an algorithm that counts in anonymous 1-interval connected networks.

Cite as

Giuseppe Di Luna and Roberto Baldoni. Non Trivial Computations in Anonymous Dynamic Networks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{diluna_et_al:LIPIcs.OPODIS.2015.33,
  author =	{Di Luna, Giuseppe and Baldoni, Roberto},
  title =	{{Non Trivial Computations in Anonymous Dynamic Networks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.33},
  URN =		{urn:nbn:de:0030-drops-66761},
  doi =		{10.4230/LIPIcs.OPODIS.2015.33},
  annote =	{Keywords: Distributed System, Anonymous Networks, Dynamic Networks}
}

Search Results

Documents authored by Di Luna, Giuseppe

Non Trivial Computations in Anonymous Dynamic Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message